package com.cqs.leetcode.math;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * lixw
 * 2021/11/3
 **/
public class RappingRainWater42 {



    public int trap(int[] height) {
        //从右边找到第一个比左边界
        return trap(height, 0, height.length - 1);
    }


    public int trap(int[] height, int left, int right) {
        if (left >= right) {
            return 0;
        }
        //从右找第一个比左边界大的柱子
        int tl = left+1;
        while (tl <= right && height[tl] < height[left]) {
            tl++;
        }
        //左边界是最高的柱子，考虑从右边界，从右边找第一个比右边界高的元素
        if (tl > right) {
            int tr = right-1;
            while (tr >= left && height[tr] < height[right]) {
                --tr;
            }
            //左侧的柱子最高的话，一定存在左边的柱子比右边界柱子高的情况
            return area(height, tr, right) + trap(height, left, tr);
        } else { //右边有柱子不低于左边界柱子
            return area(height, left, tl) + trap(height, tl, right);
        }
    }

    private int area(int[] height, int left, int right) {
        if (left >= right) return 0;
        int area = Math.min(height[left], height[right]) * (right - left+1);
        area -= 2 * Math.min(height[left], height[right]);
        for (int i = left + 1; i < right; i++) {
            area -= height[i];
        }
        return area;
    }

    public static class SolutionDp{
        public int trap(int[] height) {
            int[] leftMax = new int[height.length];
            int[] rightMax = new int[height.length];
            int lmax = 0;
            int rmax = 0;
            for (int i = 0; i < height.length; i++) {
                lmax = Math.max(lmax,height[i]);
                leftMax[i] = lmax;
            }
            for (int i = height.length-1; i >= 0; --i) {
                rmax = Math.max(rmax,height[i]);
                rightMax[i] = rmax;
            }

            int area = 0;
            for (int i = height.length-1; i >= 0; --i) {
                area += Math.min(leftMax[i],rightMax[i]) - height[i];
            }
            return area;
        }
    }

    public static void main(String[] args) {
        RappingRainWater42 rap = new RappingRainWater42();
        SolutionDp dp = new SolutionDp();
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
        list.add(new int[]{4,2,0,3,2,5});
        list.add(new int[]{1,2,3,4,5,6});
        list.add(new int[]{1,1});
        list.add(new int[]{1});
        list.add(new int[]{3,2,1});
        for (int[] c : list) {
            int trap = rap.trap(c);
            System.out.println(ArraysUtils.formatInts(c)+" ===> " + trap);
            System.out.println(ArraysUtils.formatInts(c)+" ===> " + dp.trap(c));
        }

    }

}
